//题目:
// 如果序列 X_1, X_2, ..., X_n 满足下列条件，就说它是 斐波那契式 的：n >= 3对于所有 i + 2 <= n，都有 X_i + X_{i+1} = X_{i+2}
// 给定一个严格递增的正整数数组形成序列 arr ，找到 arr 中最长的斐波那契式的子序列的长度。如果一个不存在，返回  0 。
// （回想一下，子序列是从原序列 arr 中派生出来的，它从 arr 中删掉任意数量的元素（也可以不删），而不改变其余元素的顺序。
// 例如， [3, 5, 8] 是 [3, 4, 5, 6, 7, 8] 的一个子序列）

// 示例 1：
// 输入: arr = [1,2,3,4,5,6,7,8]
// 输出: 5
// 解释: 最长的斐波那契式子序列为 [1,2,3,5,8] 。

// 示例 2：
// 输入: arr = [1,3,7,11,12,14,18]
// 输出: 3
// 解释: 最长的斐波那契式子序列有 [1,11,12]、[3,11,14] 以及 [7,11,18] 。
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
//代码
class Solution 
{
public:

    int lenLongestFibSubseq(vector<int>& arr) 
    {
        //1.创建dp表————dp[i]表示：以arr[i]为结尾的所有的子序列中，最长斐波那契子序列的长度;
        vector<int> dp(arr.size(),1);
        unordered_map<int,int> hash;//建立arr[i]——>i的映射关系
        //2.初始化
        hash[arr[0]]=0;
        hash[arr[1]]=1;
        //3.填表————动态转移方程：
        for(int i=2;i<arr.size();i++)//固定最右边的值
        {
            int max_value=1;
            for(int j=i-1;j>=0;j--)//固定中间值
            {
                dp[i]=2;
                int right=arr[i],mid=arr[j],left=right-mid,pos=j;
                while(hash.count(left) && hash[left]<pos)//寻找最左边的值
                {
                    //如果找到最左边的元素，则更新
                    dp[i]++;
                    right=mid;
                    mid=left;
                    pos=hash[mid];

                    left=right-mid;
                }
                max_value=max(max_value,dp[i]);
            }
            if(max_value==2) dp[i]=1;
            else dp[i]=max_value;

            hash[arr[i]]=i;
        }
        //4.确定返回值
        int ret=0;
        for(int i=0;i<arr.size();i++)
            ret=max(ret,dp[i]);
        return ret<3?0:ret;
    }
};